iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 3
1
自我挑戰組

神羅天征! 一起(爆肝)征服程式解題系列 第 3

[Day 3] POJ - 2431 Expedition

  • 分享至 

  • xImage
  •  

本篇同步發布於Blog: [解題] POJ - 2431 Expedition

平台:

PKU Online Judge

題號:

2431 - Expedition

題目連結:

http://poj.org/problem?id=2431

題目說明:

  有一輛車子要開往城鎮,距離為L單位,且車上目前有P單位的燃料。路上會有N(1 <= N <= 10000)間的加油站,每間加油站距離城鎮x單位、並能補充p單位的燃料。車子每行駛1單位的距離就得消耗1單位的燃料,而車子的燃料容量無限大,求車子抵達城鎮時的最少加油次數,如果達不到則輸出-1。

  範例輸入是4間加油站,需要在第1家(15 10)和第2家(11 5)加油站加油,才能抵達成鎮。

範例輸入:

4
4 4
5 2
11 5
15 10
25 10

範例輸出:

2

解題方法:

  這題需轉換問題,可以看成是當車子開到某站時,如果行經距離超過燃料箱的油量,則檢查經過的加油站的備用油,先從最大量的油倒進燃料箱,直到超過消耗量或者仍無法滿足消耗量。

        最大量的油的儲存方式是使用Priority Queue。

  以範例輸入來看:

  1. 目前距離25,到下一間加油站15,花10單位的燃料,沒有超過燃料箱的油量(10),則當前油量變成0、備用的加油站多了[10]的油量
  2. 目前距離15,到下一間加油站11,花4單位的燃料,超過燃料箱的油量(0),則拿備用油[10]倒進來,滿足這段行使距離。當前油量變成6、備用的加油站是[5]的油量 
  3. 目前距離11,到下一間加油站5,花6單位的燃料,沒有超過燃料箱的油量(6),則當前油量變成0、備用的加油站多了[2]的油量
  4. 目前距離5,到下一間加油站4,花1單位的燃料,超過燃料箱的油量(0),則拿備用油[5]倒進來,滿足這段行駛距離。當前油量變成4、備用的加油站是[4]的油量
  5. 目前距離4,到終點城鎮0,花4單位的燃料,沒有超過燃料箱的油量(4),則當前油量變成0。
  6. 需加2次油才可抵達城鎮

  題目測資會有些陷阱,比如加油站的位置不一定由小到大,需要自己排序。或者加油站的補給量有可能是0.......很好玩的測資。

  實作也把城鎮當作最後一家加油站,這樣距離/扣油量的計算才會完整。

難度為Medium

程式碼:

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Stop{
	int dist, amount;
};

bool cmp(const Stop &a, const Stop &b)
{
    return a.dist < b.dist;
}

int main() {
	int n;
	Stop stops[10005];
	int L, curAmount;
	while(cin >> n){
		int ans = 0;
		bool notToTown = false;
		priority_queue<int, vector<int>, less<int> > q;
		for(int i = 0 ; i < n;++i){
			cin >> stops[i].dist >> stops[i].amount;
		}

		cin >> L >> curAmount;
		
		
		stops[n].dist = 0;
		stops[n].amount = 0;
		
		sort(stops, stops + (n+1), cmp);
		
		int curLength = L;
		
		for(int i = n ; i >= 0;--i){
			int curDistance = curLength - stops[i].dist;
			
			while(curAmount - curDistance < 0){
				if(q.empty()){
					notToTown = true;
					break;
				}else{
					curAmount += q.top();
					q.pop();
					ans++;
				}
			}
			
			curAmount -= curDistance;
			q.push(stops[i].amount);
			curLength = stops[i].dist;
		}
		
		if(notToTown){
			cout << "-1" << endl;
		}
		else{
			cout << ans << endl;
		}
	}
	return 0;
}

GITHUB位置:

https://github.com/u8989332/ProblemSolving/blob/master/PKUOnlineJudge/2400-2499/2431.cpp


上一篇
[Day 2] LeetCode - 455 Assign Cookies
下一篇
[Day 4] UVa - 548 Tree
系列文
神羅天征! 一起(爆肝)征服程式解題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言